package DARP;

import java.util.ArrayList;
import java.util.LinkedList;
import DARP.Rota;

public class DARP3 {
	//COmentarios
	//Classes
	private Data data = Data.getPRVData();

	private LinkedList<Location> vetorDosPontos = new LinkedList<Location>();//Apenas para referenciar 
	private ArrayList<Rota> solucao = new ArrayList<Rota>();//Armazean todas as rotas da solucao

	private float[] e_Location = data.getInicioJanela(), l_Location = data.getFimJanela(), 
	s_Location = data.getTempoServico(), coordX = data.getCoordX(), coordY = data.getCoordY();

	private int[] id_Location = data.getId(), acao_Location = data.getAcao();
	private int maxIter,  maxIterILS,  kpMax,  delta;
	private float funcaoObjetivo, w0 = 1, w1 = 1, w2 = 1, w3 = 1, w4 = 1, b0 = 1, b1 = 1, b2 = 1, b3 = 1, b4 = 1;

	//variaveis inteiras
	private int qntVeiculos = data.getQuantidadeDeVeiculos(), 
	qntPontos = data.getQuantidadeDePontosDeColetas(),
	W_TempoMaximo_Espera, limiteDosEmbarques = (data.getQuantidadeDePontosDeColetas()/2),
	tempMaxCaronaCliente_R = data.getTempoMaxDeViagemCliente(),
	cargaMaximaDoVeiculo = data.getCapacidadeDoVeiculo();
	private int[] capacidadeVeiculo = data.getCapacidadeDosVeiculos(), 
	garagemInicial = data.getGaragensIniciais(), 
	garagemFinal = data.getGaragensFinais();;

	private float[][] matrizDistancia = data.getMatriz(), t = data.getT();

	/**
	 * Constrói o vetor dos pontos para termos uma referência
	 * 
	 * @param tempoMaximoDeEsperaDoVeiculo_W
	 */
	public void carregaDados(int tempoMaximoDeEsperaDoVeiculo_W){//Constrói o vetor com os dados para referencia
		//		float[] e_Location = data.getInicioJanela(), l_Location = data.getFimJanela(), 
		//		s_Location = data.getTempoServico(), coordX = data.getCoordX(), coordY = data.getCoordY();
		//
		//		int[] id_Location = data.getId(), acao_Location = data.getAcao();

		data.getPRVData();

		System.out.println("======================= Leu os dados ========================");

		for (int i = 0; i < qntPontos +2; i++) {
			Location location = new Location(coordX[i], coordY[i], e_Location[i], l_Location[i], s_Location[i],id_Location[i], acao_Location[i]);
			vetorDosPontos.add(id_Location[i], location);
			//vetorVisitados[i] = false;
			W_TempoMaximo_Espera = tempoMaximoDeEsperaDoVeiculo_W;
		}

		System.out.println(" ======================== Os dados foram carregados com sucesso ========================");
	}//Fim carregaDados


	public void inicializaRotas(){//Cria as rotas vazias
		//int contVeiculos = 0;
		System.out.println(" ======================== Inicio do Inicializa Rotas  ========================");
		float zero = 0;
		for (int k = 0; k < qntVeiculos; k++) { 
			//Adiciona a lista de variaveis as variaveis A B D R W T Q F
			LinkedList<Integer> rota = new LinkedList<Integer>(), acao = new LinkedList<Integer>();//int[2*capacidadeVeiculo[k]];//int[2*capacidadeVeiculo[contVeiculos]];//Vetor com os ids das requisicoes e das variaveis
			LinkedList<Float>  A = new LinkedList<Float>(), B = new LinkedList<Float>(), D = new LinkedList<Float>(), 
			W = new LinkedList<Float>(), R = new LinkedList<Float>(), T = new LinkedList<Float>(), Q = new LinkedList<Float>(),
			F = new LinkedList<Float>();

			for (int i = 0; i < (2 + 2*capacidadeVeiculo[k]) ; i++) {//Inicializa as listas de valores das variaveis
				rota.add(i, -1);
				A.add(zero);
				B.add(zero);
				D.add(zero);				
				R.add(zero);				
				W.add(zero);				
				T.add(zero);				
				Q.add(zero);				
				F.add(zero);

			}

			rota.set(0, garagemInicial[k]);
			rota.set( (1 + 2*capacidadeVeiculo[k]) , garagemFinal[k]);

			Rota rotaVeiculo = new Rota(rota, A, B, D, W, R, T, Q, F);//, e, l, acao, s, tempMaxCaronaCliente_R, tempoMaxDaRotaVeiculo, cargaMaximaDoVeiculo);	
			//			System.out.println("Rota Adicionada a Solucao");
			solucao.add(rotaVeiculo);
			//			System.out.println("A de"+k+" Tamanho: "+A.size()+">>" +A.toString());
			//			System.out.println("B de"+k+" Tamanho: "+B.size()+">>" +B.toString());
			//			System.out.println("D de"+k+" Tamanho: "+D.size()+">>" +D.toString());
			//			System.out.println("R de"+k+" Tamanho: "+R.size()+">>" +R.toString());
			//			System.out.println("w de"+k+" Tamanho: "+W.size()+">>" +W.toString());
			//			System.out.println("T de"+k+" Tamanho: "+T.size()+">>" +T.toString());
			//			System.out.println("Q de"+k+" Tamanho: "+Q.size()+">>" +Q.toString());
			//			System.out.println("F de"+k+" Tamanho: "+F.size()+">>" +F.toString());

		}

		System.out.println(" ======================== Rotas Inicializadas  ========================");
	}//Fim do inicializaRotas

	/**
	 * Cria uma solução inicial para ser trabalhada
	 */
	public void solucaoInicial(){
		System.out.println(" ======================== Inicio da Solucao Inicial  ========================");
		inicializaRotas();
		int qntInseridos = 0, cont = 0, indiceRandomico, nMax=  1000, adidiconarRequisicao, indiceDesembarque;////====>
		Integer elementoEmbarque, elementoDesembarque;
		LinkedList<Integer> rota;
		boolean ehPossivelInserirNasRotas = true;
		boolean[] elementosComVagas = new boolean[qntVeiculos];
		for (int i = 0; i < qntVeiculos; i++) {
			elementosComVagas[i] = true;
		}
		while(qntInseridos < qntPontos || solucao.size() == 0 ){

			indiceRandomico = (int) ((Math.random() * (qntVeiculos)));
			rota = solucao.get(indiceRandomico).getRota();//Pego uma rota

			//			System.out.println("Rota Randomica "+indiceRandomico);

			adidiconarRequisicao = data.retornaMenorDistacia(garagemInicial[indiceRandomico],matrizDistancia);
			System.out.println("O elemento retornado de "+garagemInicial[indiceRandomico]+" foi: "+ adidiconarRequisicao);
			if(adidiconarRequisicao == 999) break;//Todas as requisicoes foram adicionadas 
			cont = 0;

			//================================			
			for (int i = 1; i < (rota.size()/2); i++) {
				if( (-1) == (int)rota.get(i)  ){

					rota.set(i, adidiconarRequisicao);//Embarque
					rota.set(i+ (rota.size()/2) -1, (adidiconarRequisicao - 1 + data.getId().length/2));


					elementoEmbarque = rota.get(i);//Retorna o id
					indiceDesembarque = rota.indexOf(elementoEmbarque + limiteDosEmbarques);//Retorna o id do desembarque
					elementoDesembarque = rota.get(indiceDesembarque);//
					System.out.println(">>>Quantidade elementos inseridos >>"+qntInseridos+"<< elementosDisponiveis "+qntPontos );
					qntInseridos++;
					break;
				}else{
					if(i == (rota.size()/2 -1)){
						elementosComVagas[indiceRandomico] = false;//Tiramos o elemento da lista

						//						System.out.println("Rota "+indiceRandomico+ "nao tem mais como inserir elementos na rota");
						//						System.out.println("Rota toString "+ rota.toString());
						break;
					}
				}

			}

			//			for (int i = 0; i < qntVeiculos; i++) {
			//				cont++;
			//			
			//				for (int j = 0; j < rota.size(); j++) {
			//					
			//				
			//					if(rota.get(j) == -1){
			//						continue;
			//					}else{
			//						
			//						if(cont == qntVeiculos)
			//							System.out.println("Contador"+ cont + "QntVeiculos"+ qntVeiculos);
			//							ehPossivelInserirNasRotas = false;
			//							System.out.println("CONT>"+ cont+" >NAO TEM MAIS COMO INSERIR ELEMENTOS EM TODAS AS ROTAS!!!");
			//							break;
			//					}
			//			}
			//			}
			//if (VerificaSeViolaRestricoes()) {//Verifica se viola as restricoes caso nao viole adiciona-se a rota

			solucao.get(indiceRandomico).setRota(rota);//Adiciona o vetor de rotas a solucao de rotas
			data.setRequisicoesVisitadas(adidiconarRequisicao, (adidiconarRequisicao - 1 + data.getId().length/2));

		}
		System.out.println(" ======================== Fim da Soulucao Inicial ========================");
	}

	public void heuristicaDeProgramacao(){
		System.out.println(" ======================== Inicio da Heuristica de Programacao ========================");
		Rota rotaDaVez;

		float[] variaveisDaVez;
		int elementoInt;
		float elementoFloat;
		Location localtion;
		LinkedList<Float> A, B, D, R, W, T, Q, F, s= new LinkedList<Float>(), e = new LinkedList<Float>(), l = new LinkedList<Float>();
		LinkedList<Integer> elementosDaRota,  acao = new LinkedList<Integer>();
		int tamanhoDaRota, tempoMaxCaronaCliente_R;

		for (int k = 0; k < solucao.size(); k++) {//Para cada rota calcularemos o atraso
			rotaDaVez = solucao.get(k);
			tamanhoDaRota = rotaDaVez.getRota().size(); 
			//Para cada rota faremos
			A =  rotaDaVez.getA();
			B =  rotaDaVez.getB();
			D =  rotaDaVez.getD();
			R =  rotaDaVez.getR();
			W =  rotaDaVez.getW();
			T =  rotaDaVez.getT();				
			Q =  rotaDaVez.getQ();
			F =  rotaDaVez.getF();
			elementosDaRota = rotaDaVez.getRota();
			//e = new float[elementosDaRota.size()];
			//l = new float[elementosDaRota.size()];
			//s = new float[elementosDaRota.size()];
			//acao = new int[elementosDaRota.size()];
			int aux = 0;
			System.out.println("Rota:" + elementosDaRota.toString());
			for (int i = 0; i < elementosDaRota.size(); i++) {
				aux = elementosDaRota.get(i);//Retorna o id
				//Location local_indexDoElemento = vetorDosPontos.getLast();
				//int id = local_indexDoElemento.getId();
				// vetorDosPontos.get(indexDoElemento).getId();
				//				System.out.println("Tamanho da rota: "+ elementosDaRota.size());
				//				System.out.println("ITERACAO: "+i);
				//				System.out.println("ID: "+ aux);
				e.add(i,e_Location[aux]);
				//				System.out.println("e: "+ e_Location[aux]);
				l.add(i,l_Location[aux]);
				//				System.out.println("l: "+ l_Location[aux]);	
				s.add(i,s_Location[aux]);
				//				System.out.println("s: "+ s_Location[aux]);
				acao.add(i, acao_Location[aux]);
				//				System.out.println("acao: "+ acao_Location[aux]);
			}
			//			System.out.println("=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-==-=-");
			//			System.out.println("=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-==-=-");
			//			System.out.println("JANELAS INICIAIS "+"tamanho"+e.size()+" >>"+ e.toString());
			//			System.out.println("=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-==-=-");
			//			System.out.println("=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-==-=-");
			//			System.out.println("--------- Antes de calcularmos o atraso ----------");
			//			System.out.println("A de"+k+" Tamanho: "+A.size()+">>" +A.toString());
			//			System.out.println("B de"+k+" Tamanho: "+B.size()+">>" +B.toString());
			//			System.out.println("D de"+k+" Tamanho: "+D.size()+">>" +D.toString());
			//			System.out.println("R de"+k+" Tamanho: "+R.size()+">>" +R.toString());
			//			System.out.println("w de"+k+" Tamanho: "+W.size()+">>" +W.toString());
			//			System.out.println("T de"+k+" Tamanho: "+T.size()+">>" +T.toString());
			//			System.out.println("Q de"+k+" Tamanho: "+Q.size()+">>" +Q.toString());
			//			System.out.println("F de"+k+" Tamanho: "+F.size()+">>" +F.toString());



			tempoMaxCaronaCliente_R = this.tempMaxCaronaCliente_R;

			//			for (int i = 0; i < tamanhoDaRota; i++) {
			//				localtion = (Location) vetorDosPontos.get(elementosDaRota[i]);
			//				e[i] = localtion.getE();
			//				s[i] = localtion.getS();
			//				acao[i] = localtion.getAcao();
			//			}
			float inicial = 0;
			W.set(0, inicial); 
			A.set(0, inicial); 
			Q.set(0, inicial);//Iniciando as variaveis
			B.set(0, e.get(0));
			D.set(0, B.get(0));

			calculaVariaveis(A, B, D, W, R, Q, e, s, acao, elementosDaRota);			
			calculaFO(F,l,R,B,W, elementosDaRota, tempoMaxCaronaCliente_R);//TODO Falta acabar de implementar

			//Calcular Somatorio de Wp
			float somaWp = 0;
			somaWp = calculaSomatorioWp(somaWp,W);
			B.set(0,  e.get(0) + Math.min(F.get(0), somaWp));
			atualizaVariaveis(A, B, W, D, e, s, elementosDaRota);
			calcularR(B, D, R, elementosDaRota);//Calcular somente os pontos de embarque

			for (int i = 1; i < elementosDaRota.size(); i++) {//Calcular vo != v1 SOMENTE PARA OS PONTOS DE EMBARQUE
				//				B[i+1] = B[i] + s[i] + t[i][i+1] + W[i+1];
				calculaFO(F, l, R, B, W, elementosDaRota, tempoMaxCaronaCliente_R);//TODO IMPLEMENTAR !!
				somaWp = calculaSomatorioWp(somaWp, W);
				if(elementosDaRota.get(i) < limiteDosEmbarques )
					if(elementosDaRota.get(i) != 0){
						//int indiceDesembarque = elementosDaRota.indexOf(limiteDosEmbarques + elementosDaRota.get(i));
						//PEGAR O INDICE DO ELEMENTO APOS O LIMITE DO EMBARQUE DA ROTA
						//R[i] = B[indiceDesembarque ]- D[i];//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P

						B.set(i, B.get(i) + Math.min(F.get(i), somaWp));
						D.set(i, B.get(i) + s.get(i));
						W.set(i, B.get(i) - A.get(i));

						atualizaVariaveis(A, B, W, D, e ,s,elementosDaRota);
						atualizaR(B, D, R, elementosDaRota);
					}
			}

			//			System.out.println("--------- Depois de calcularmos o atraso ----------");
			//			System.out.println("A de"+k+" Tamanho: "+A.size()+">>" +A.toString());
			//			System.out.println("B de"+k+" Tamanho: "+B.size()+">>" +B.toString());
			//			System.out.println("D de"+k+" Tamanho: "+D.size()+">>" +D.toString());
			//			System.out.println("R de"+k+" Tamanho: "+R.size()+">>" +R.toString());
			//			System.out.println("w de"+k+" Tamanho: "+W.size()+">>" +W.toString());
			//			System.out.println("T de"+k+" Tamanho: "+T.size()+">>" +T.toString());
			//			System.out.println("Q de"+k+" Tamanho: "+Q.size()+">>" +Q.toString());
			//			System.out.println("F de"+k+" Tamanho: "+F.size()+">>" +F.toString());


		}//Fim do for para obtermos cada veículo


		System.out.println(" ======================== Fim da Heuristica de Programacao ========================");
	}//Fim da Heuristica de Programacao

	private void atualizaR(LinkedList<Float> b, LinkedList<Float> d, LinkedList<Float> r,	LinkedList<Integer> elementosDaRota2) {
		for (int i = 1; i < elementosDaRota2.size(); i++) {//P e U

			//			if(elementosDaRota2.get(i) < limiteDosEmbarques){
			//				R[i] = B[limiteDosEmbarques + i]- D[i];//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P
			//			}
			if(elementosDaRota2.get(i) < limiteDosEmbarques )
				if(elementosDaRota2.get(i) != 0){
					int indiceDesembarque = elementosDaRota2.indexOf(limiteDosEmbarques + elementosDaRota2.get(i));
					//PEGAR O INDICE DO ELEMENTO APOS O LIMITE DO EMBARQUE DA ROTA
					r.set(i, b.get(indiceDesembarque) - d.get(i));//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P
				}
		}

	}

	private float calculaSomatorioWp(float somaWp, LinkedList<Float> w) {
		for (int z = 1; z < w.size(); z++) {
			somaWp += w.get(z);
		}
		return somaWp;
	}

	private void calcularR(LinkedList<Float> b, LinkedList<Float> d, LinkedList<Float> r, LinkedList<Integer> elementosDaRota2){
		for (int i = 1; i < elementosDaRota2.size(); i++) {//P e U
			if(elementosDaRota2.get(i) < limiteDosEmbarques )
				if(elementosDaRota2.get(i) != 0){
					int indiceDesembarque = elementosDaRota2.indexOf(limiteDosEmbarques + elementosDaRota2.get(i));
					//PEGAR O INDICE DO ELEMENTO APOS O LIMITE DO EMBARQUE DA ROTA
					r.set(i, b.get(indiceDesembarque)- d.get(i));//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P
				}
			//			if(elementosDaRota2.get(i) < limiteDosEmbarques){
			//				R[i] = B[limiteDosEmbarques + i]- D[i];//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P
			//			}
		}
	}

	private void atualizaVariaveis(LinkedList<Float> a, LinkedList<Float> b, LinkedList<Float> w , LinkedList<Float> d, LinkedList<Float> e, LinkedList<Float> s, LinkedList<Integer> elementosDaRota2){
		for (int i = 1; i < elementosDaRota2.size() -1; i++) {//P e U
			a.set(i, d.get(i-1) + t[i-1][i]);//Para P U G+
			b.set(i, Math.max(e.get(i), a.get(i)));//Para P U G+
			if(a.size() != i){
				d.set(i, b.get(i) + s.get(i)); //Para P e U
			}else{
				d.set(i, b.get(i));//Para G+
			}	
			w.set(i, b.get(i) - a.get(i)); // Para P U G+

		}

	}

	private void calculaFO(LinkedList<Float> f, LinkedList<Float> l, LinkedList<Float> r, LinkedList<Float> b, LinkedList<Float> w, LinkedList<Integer> elementosDaRota2, int tempoMaxCaronaCliente_R) {//Calcula o atraso
		int somatorioW = 0;
		float minimoFO, zero = 0;;

		for (int j = 0; j < elementosDaRota2.size(); j++) {
			minimoFO = Integer.MAX_VALUE;
			if(j != 0 && j<=limiteDosEmbarques ){
				for (int p = 0; p < j; p++) {
					somatorioW += w.get(p);
				} 
				if(minimoFO > (somatorioW + Math.min(l.get(j) - b.get(j),  tempoMaxCaronaCliente_R - r.get(j))))//TODO Verificar o R~
					minimoFO = (somatorioW + Math.min(l.get(j) - b.get(j), tempoMaxCaronaCliente_R - r.get(j)));


				f.set(0, Math.min(somatorioW, minimoFO));
			}else
				if(j == 0){ 
					for (int p = 0; p < j; p++) {
						somatorioW += w.get(p);
					} 
					if(minimoFO > (somatorioW + Math.min(l.get(j) - b.get(j), tempoMaxCaronaCliente_R - r.get(j))))//TODO Verificar o R~
						minimoFO = (somatorioW + Math.min(l.get(j) - b.get(j), tempoMaxCaronaCliente_R - r.get(j)));
					f.set(j,  Math.min(somatorioW, minimoFO));
				}else
					f.set(j, zero);
		}
	}

	private void calculaVariaveis(LinkedList<Float> a, LinkedList<Float> b, LinkedList<Float> d, LinkedList<Float> w, LinkedList<Float> r, LinkedList<Float> q, LinkedList<Float> e, LinkedList<Float> s,  LinkedList<Integer> acao, LinkedList<Integer> elementosDaRota2){
		for (int i = 1; i < elementosDaRota2.size(); i++) {//P e U
			a.set(i,  d.get(i-1) + t[i-1][i]);//Para P U G+
			b.set(i,  Math.max(e.get(i), a.get(i)));//Para P U G+
			if(a.size() != i){
				d.set(i,  b.get(i) + s.get(i)); //Para P e U
				q.set(i, q.get(i-1) + acao.get(i));

			}else{
				d.set(i,  b.get(i));//Para G+
				float zero = 0;
				q.set(i, zero);
			}	
			w.set(i, b.get(i) - a.get(i)); // Para P U G+
			if(elementosDaRota2.get(i) < limiteDosEmbarques )
				if(elementosDaRota2.get(i) != 0){
					int indiceDesembarque = elementosDaRota2.indexOf(limiteDosEmbarques + elementosDaRota2.get(i));
					//PEGAR O INDICE DO ELEMENTO APOS O LIMITE DO EMBARQUE DA ROTA
					r.set(i, b.get(indiceDesembarque) - d.get(i));//TODO FAZER UMA VAR GLOBAL P LIMITE PARA P
				}
		}
	}

	//Calcula Funcao Objetivo
	public float calculaFuncaoObjetivo(ArrayList<Rota> solucao){
		System.out.println(" ======================== Inicio do Calcula Funcao Objetivo ========================");
		float  termoUmUm = 0, termoUmDois = 0, termoUmTres = 0, termoUmQuatro = 0, termoUmCinco = 0, //Os termos estao conforme a funcao
		termoDoisUm = 0 , termoDoisDois = 0, termoDoisTres = 0, 
		termoTresUm = 0, termoTresDois = 0;
		LinkedList<Integer> elementosDaRota;
		LinkedList<Float> B , D, W, R, T, Q, e = new LinkedList<Float>(), l = new LinkedList<Float>();

		for (int k = 0; k < solucao.size(); k++) {
			//			System.out.println("CALCULA FO =="+k+"= de ="+(solucao.size()-1));
			Rota rota = solucao.get(k);
			elementosDaRota = rota.getRota();
			B = rota.getB();
			D = rota.getD();
			W = rota.getW();
			//			System.out.println("R com "+rota.getR().size() + ">>"+rota.getR().toString());
			R = rota.getR();
			T = rota.getT();
			Q = rota.getQ();
			//			e = rota.getE();
			//			l = rota.getL();

			Integer aux = 0;
			for (int i = 0; i < elementosDaRota.size(); i++) {
				aux = elementosDaRota.get(i);//Retorna o id

				e.add(i,e_Location[aux]);
				l.add(i,l_Location[aux]);
				//				s.add(i,s_Location[aux]);
				//				acao.add(i, acao_Location[aux]);
			}
			//Somatorio das distancias
			for (int i = 0; i < elementosDaRota.size(); i++) {
				termoUmUm += matrizDistancia[elementosDaRota.get(i)][elementosDaRota.get(i)];	
			}

			//Somatorio dos veiculos
			termoUmDois += 1;
			//Somatorio dos tempos de inicio da viagem da garagem inicial menos o tempo de chegada na garagem final
			termoUmTres +=  B.get(elementosDaRota.get(0)) - D.get(elementosDaRota.get((elementosDaRota.size() - 1)));


			for (int i = 1; i < elementosDaRota.size() -1; i++) {//Tiramos as garagens
				if (elementosDaRota.get(i) < limiteDosEmbarques) {//i E P
					//Somatorio do tempo de viagem
					termoUmQuatro += R.get(i);		
				}
				//Somatorio do tempo de espera
				termoUmCinco += W.get(i);//TODO DEU PAU AQUI !!! ===================>
			}
			//==================== Passamos para o segundo termo
			//Calcula o somatorio 
			termoDoisUm += Math.max(0, 
					(B.get(0) - D.get(elementosDaRota.size()-1)) - rota.getTempoMaxDaRotaVeiculo());

			//Calcula o somatorio
			int tempoMaxViagemCliente = rota.getTempoMaxDeViagemPermitidoCliente();

			for (int i = 1; i < elementosDaRota.size() -1; i++) {
				if(elementosDaRota.get(i) < limiteDosEmbarques)
					termoDoisDois += Math.max(0, (R.get(i) - tempoMaxViagemCliente));
			}

			//Calcula o somatorio
			//float[] tempoMaxEsperaNoPonto = rota.getTempoMaximoDeEspera();

			for (int i = 1; i < elementosDaRota.size() -1; i++) {
				if(elementosDaRota.get(i) < limiteDosEmbarques)
					termoDoisTres += Math.max(0, 
							(W.get(i) - W_TempoMaximo_Espera));
			}

			//TODO Calculo do Q E Q~
			float somatorio = 0; 
			int[] acao = acao_Location;
			System.out.println("A Carga Máxima do veículo é "+ cargaMaximaDoVeiculo);
			for (int i = 1; i < elementosDaRota.size(); i++) {
				
				System.out.println("ELemento de tamanho"+ elementosDaRota.size()+"esta em "+i);
				//				for (int j = 1; j < elementosDaRota.size()-1; j++) {
				//					if(i!= j && j != limiteDosEmbarques - i){
				somatorio += acao[elementosDaRota.get(i)];
				System.out.println("Termo "+i+"eh "+somatorio);
				//						System.out.println("Acao "+acao[elementosDaRota.get(i)]);
				//					}
				//				}
			}
			termoTresUm += Math.max(0, somatorio - cargaMaximaDoVeiculo);




			//			for (int i = 1; i < elementosDaRota.size()-1; i++) {
			//				float somatorio = 0; int[] acao = acao_Location;
			//				System.out.println("ELemento de tamanho"+ elementosDaRota.size()+"esta em "+i);
			//				for (int j = 1; j < elementosDaRota.size()-1; j++) {
			//					if(i!= j && j != limiteDosEmbarques - i){
			//						somatorio += acao[elementosDaRota.get(i)];
			//						System.out.println("Acao "+acao[elementosDaRota.get(i)]);
			//					}
			//				}
			//				termoTresUm += Math.max(0, somatorio - cargaMaximaDoVeiculo);
			//				System.out.println("Termo "+i+"eh "+somatorio);
			//
			//			}

			//Somatorio 
			for (int i = 0; i < elementosDaRota.size(); i++) {
				termoTresDois += Math.max(0, e.get(i) - B.get(i)) + Math.max(0, B.get(i) - l.get(i)); 
			}

			//			funcaoObjetivo =termoUmUm() + w1*termoUmDois()+termoUmTres()+termoUmQuatro()+termoUmCinco();
			funcaoObjetivo = w0*termoUmUm + w1*termoUmDois + w2*termoUmTres + w3*termoUmQuatro + w4*termoUmCinco + 
			b0*termoDoisUm + b1*termoDoisDois + b2*termoDoisTres + 
			b3*termoTresUm	
			+ b4*termoTresDois;
		}
		System.out.println(" ======================== Fim do Calcula Funcao Objetivo ========================");
		return funcaoObjetivo;
	}//Fim do Calculo da Funcao Objetivo

	//Meta Heuristica ILS-MRD
	public void ILS(int maxIter, int maxIterILS, int kpMax, int delta){
		System.out.println(" ======================== Inicio do ILS ========================");
		this.maxIter = maxIter; this.maxIterILS = maxIterILS; 
		this.kpMax = kpMax; this.delta = delta;

		ArrayList<Rota> s_linha = new ArrayList<Rota>(); //Solucao s' conjunto de rotas
		ArrayList<Rota> s_duaslinhas = new ArrayList<Rota>();//Solucao s'' conjunto de rotas
		solucaoInicial();//Cria a solucao inicial 
		heuristicaDeProgramacao();
		ArrayList<Rota> so = solucao;//Atribue a so a solucao inicial
		s_linha = MRD(so, maxIterILS);	

		//solucaoInicial();

		int kp = 0;
		int iter = 0, melhorIter = 0;
		System.out.println("Inicia o primeiro While");
		while (kp < kpMax){
			iter = melhorIter;
			System.out.println("Inicia o Segundo While");
			while(iter < maxIter){
				iter = iter + 1;
				System.out.println("Iteracao ILS eh: "+iter+" ================");
				//TODO Perturbqacao
				s_linha = pertubacao(s_linha);
				s_duaslinhas = MRD(so, maxIterILS);//TODO METODO DO MRD
				heuristicaDeProgramacao();
				float s_linhaFO = calculaFuncaoObjetivo(s_linha), s_duasLinhasFO = calculaFuncaoObjetivo(s_duaslinhas);
				if ( s_linhaFO < s_duasLinhasFO ){
					s_linha = s_duaslinhas;
					melhorIter = iter;
					kp = 0;
				}
			}
			kp = kp + delta;
		}

		System.out.println("Valor da função objetivo é: "+funcaoObjetivo);
		System.out.println("Rotas ==>>");
		imprimeRotas(s_linha);
		System.out.println(" ======================== Fim do ILS ========================");
	}

	private void imprimeRotas(ArrayList<Rota> sLinha) {

		for (int i = 0; i < sLinha.size(); i++) {
			System.out.println(sLinha.get(i).getRota().toString()+"Tamanho eh: "+ sLinha.get(i).getRota().size());
		}
	}


	private ArrayList<Rota> MRD(ArrayList<Rota> so, int maxIterILS) {
		// TODO Auto-generated method stub
		System.out.println(" ======================== Inicio do MRD ========================");
		int iter = 0;
		float foSLinha = 0, foSO = 0;
		while(iter < maxIterILS){
			iter = iter + 1;
			System.out.println("Iteracao n "+ iter);
			ArrayList<Rota> s_linha = new ArrayList<Rota>(); 
			s_linha = geraAleatoriamente(so);
			foSLinha = calculaFuncaoObjetivo(s_linha);
			foSO = calculaFuncaoObjetivo(so);
			if(foSLinha < foSO){//(calculaFuncaoObjetivo(s_linha) < calculaFuncaoObjetivo(so)){
				so = s_linha;//
				iter = 0;
			}
		}
		System.out.println(" ======================== Fim do MRD ========================");

		return so;
	}


	private ArrayList<Rota> geraAleatoriamente(ArrayList<Rota> so) {
		System.out.println(" ======================== Inicio Gera Aleatoriamente ========================");
		int opcaoRandomica = (int) ((Math.random() * 4));

		switch (opcaoRandomica) {
		case 0:

			reordenarRota(so); //OK
			break;

		case 1:
			realocaPonto(so);//OK
			break;

		case 2:
			trocaPontos(so);//OK
			break;

		default:
			realocaBlocosEmbarque(so);
			break;
		}
		System.out.println(" ======================== Fim do Gera Aleatoriamente ========================");
		return so;
	}
	//llll
	private ArrayList<Rota> pertubacao(ArrayList<Rota> sLinha) {
		//TODO Chamar o CPLEX para atuar nas duas piores rotas 
		reordenarRota(sLinha);

		return sLinha;
	}

	//==========================================================>

	/*
	 *     ESTRUTURAS DAS VIZINHANCAS
	 */

	/**
	 * 
	 * @param so
	 * @return
	 */
	public ArrayList<Rota> reordenarRota(ArrayList<Rota> so){
		System.out.println(" ======================== Inicio Reordena Rota ========================");
		int nRota1Randomica = (int) ((Math.random() * so.size())), indiceRandomico,  indiceEmbarque, indiceDesembarque;
		LinkedList<Integer> rota1 = so.get(nRota1Randomica).getRota();//Seleciona uma rota aleatoria
		if(rota1.size() <= 4){//S� ter� uma requisicao e as garagens
			return so;
		}
		do{
			indiceRandomico = (int)(1+ (Math.random() * (rota1.size()-2)));//Somente os embarques e desembarques//(int)( (Math.random() * rota1.size()));//Seleciona qualquer um dos pontos da rota
		}while(indiceRandomico == rota1.size()  );

		//		System.out.println("Indice Randomico: " + indiceRandomico+" tamanho da rota "+ rota1.size());
		Integer elementoTroca = rota1.get(indiceRandomico), desembarqueElemento, embarqueElemento;			
		//		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		//		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		//		System.out.println("Rota a"+ rota1.toString()+"antes da insercao do Reordena Rota ");
		//		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		//		System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");

		do{//Verifica se o indice do elemento original foi igual ao indice gerado
			indiceEmbarque = (int)(1+ (Math.random() * (rota1.size()-2)));//Somente os embarques e desembarques;
			indiceDesembarque =  (int)(1+ (Math.random() * (rota1.size()-2)));//Somente os embarques e desembarques
		}while((indiceRandomico == indiceEmbarque) || 
				(indiceEmbarque >= indiceDesembarque ) || 
				(indiceDesembarque >= (rota1.size()-1)));

		//		System.out.println("Indice Embarque: "+indiceEmbarque);
		//		System.out.println("Indice Desembarque: "+indiceDesembarque);
		//		System.out.println("Elemento: " + elementoTroca);
		if(elementoTroca < limiteDosEmbarques){//O Id eh Embarque
			rota1.remove(elementoTroca);
			desembarqueElemento = elementoTroca + limiteDosEmbarques;
			rota1.remove(desembarqueElemento);
			rota1.add(indiceEmbarque, elementoTroca);//Embarque
			rota1.add(indiceDesembarque, elementoTroca + limiteDosEmbarques);//Desembarque

		}else{//O Id eh Desembarque
			embarqueElemento = elementoTroca - limiteDosEmbarques;
			rota1.remove(embarqueElemento);
			rota1.remove(elementoTroca);
			rota1.add(indiceEmbarque, embarqueElemento);//Embarque
			rota1.add(indiceDesembarque, elementoTroca);//Desembarque
		}
		//		System.out.println("//////////////////////////////////////////////////////////");
		//		System.out.println("//////////////////////////////////////////////////////////");
		//		System.out.println("Rota d"+ rota1.toString()+"apos a insercao do Reordena Rota ");
		//		System.out.println("//////////////////////////////////////////////////////////");
		//		System.out.println("//////////////////////////////////////////////////////////");
		so.get(nRota1Randomica).setRota(rota1);
		System.out.println(" ======================== Fim do Reordena Rota ========================");
		return so;
	}

	/**
	 * 
	 * @param so
	 * @return
	 */
	public ArrayList<Rota> realocaPonto(ArrayList<Rota> so){
		System.out.println(" ======================== Inicio Realoca Rota ========================");

		int nRota1Randomica = (int) ((Math.random() * so.size())), nRota2Randomica, indiceEmbarque, posicaoRandomica, indiceDesembarque;
		Integer elementoDesembarque, elementoEmbarque; 
		do{
			nRota2Randomica = (int) ((Math.random() * so.size()));

			//			System.out.println("nRota1 " + nRota1Randomica);
			//			System.out.println("nRota2 " + nRota2Randomica);
			//			
		}while(nRota1Randomica == nRota2Randomica);

		LinkedList<Integer> rota1 = so.get(nRota1Randomica).getRota(), 
		rota2 = so.get(nRota2Randomica).getRota();//Seleciona uma rota aleatoria


		if( rota1.size() == 2 ||  rota2.size() == 2){
			return so;
		}
		//		System.out.println("Rota 1 : "+ rota1.toString()+ " tamanho �: "+ rota1.size());
		//		System.out.println("Rota 2 : "+ rota2.toString()+ " tamanho �: "+ rota2.size());

		do{
			indiceEmbarque = (int)(1+ (Math.random() * (rota1.size() - 2)));//Seleciona qualquer um dos pontos da rota
			elementoEmbarque = rota1.get(indiceEmbarque);
		}while(elementoEmbarque > limiteDosEmbarques);

		elementoDesembarque = (rota1.get(indiceEmbarque) + limiteDosEmbarques);
		indiceDesembarque = rota1.indexOf(elementoDesembarque);


		//		System.out.println("Indice de embarque a remover " + indiceEmbarque + " Incide desembarque a remover "+ indiceDesembarque);		
		//		System.out.println("Elemento a remover embarque "+rota1.get(indiceEmbarque).toString()+ " desembarque "+ elementoDesembarque.toString() );


		rota1.remove(elementoEmbarque);// .remove(indiceEmbarque); //Remove os elementos de embarque e desembarque
		rota1.remove(elementoDesembarque);//indiceDesembarque);

		so.get(nRota1Randomica).removetA(indiceEmbarque);
		so.get(nRota1Randomica).removetB(indiceEmbarque);
		so.get(nRota1Randomica).removetD(indiceEmbarque);
		so.get(nRota1Randomica).removetR(indiceEmbarque);
		so.get(nRota1Randomica).removetW(indiceEmbarque);
		so.get(nRota1Randomica).removetQ(indiceEmbarque);
		so.get(nRota1Randomica).removetT(indiceEmbarque);
		so.get(nRota1Randomica).removetF(indiceEmbarque);

		//Removendo "e, l , s ,acao" do desembarque
		so.get(nRota1Randomica).removetA(indiceDesembarque);
		so.get(nRota1Randomica).removetB(indiceDesembarque);
		so.get(nRota1Randomica).removetD(indiceDesembarque);
		so.get(nRota1Randomica).removetR(indiceDesembarque);
		so.get(nRota1Randomica).removetW(indiceDesembarque);
		so.get(nRota1Randomica).removetQ(indiceDesembarque);
		so.get(nRota1Randomica).removetT(indiceDesembarque);
		so.get(nRota1Randomica).removetF(indiceDesembarque);



		//		System.out.println("Removeu !!!!!!!");
		//		System.out.println("Rota 1 : "+ rota1.toString()+" removidos, ??tamanho "+ rota1.size());
		//		System.out.println("Rota 2 : "+ rota2.toString()+" removidos ??tamanho "+ rota2.size());
		//		===== OK ATE AQUI
		//		System.out.println("Tudo ok ate aqui");
		//		if(rota2.size() == 2)
		do{
			indiceEmbarque = (int)(1+ (Math.random() * (rota2.size() - 2)));//Seleciona qualquer um dos pontos da rota
			indiceDesembarque = (int)(1+ (Math.random() * (rota2.size() - 2)));//Seleciona qualquer um dos pontos da rota
			//			elementoEmbarque = rota2.get(indiceEmbarque);
			//			elementoDesembarque = rota2.get(indiceDesembarque);
			//			System.out.println("Rota no laco >>> "+rota2.toString());
			//			System.out.println("Indice embaruqe "+indiceEmbarque + "Para inser�ao"+elementoEmbarque);
			//			System.out.println("Indice desembaruqe "+indiceDesembarque + "Para inser�ao"+elementoDesembarque);

		}while(indiceEmbarque>= indiceDesembarque);//elementoEmbarque <= elementoDesembarque);
		//				elementoEmbarque > limiteDosEmbarques && elementoDesembarque < limiteDosEmbarques && elementoEmbarque > elementoDesembarque);
		//		System.out.println("Indice embaruqe "+indiceEmbarque + "=====>>> Para inser�ao"+elementoEmbarque);
		//		System.out.println("Indice desembaruqe "+indiceDesembarque + "=====>>> Para inser�ao"+elementoDesembarque);
		//		
		//		
		//		System.out.println("Rota 1 : "+ rota1.toString());
		//		System.out.println("Rota 2 : "+ rota2.toString());
		//		System.out.println("Elemento de embarque "+ elementoDesembarque.toString());
		//		System.out.println("Indice de embarque " + indiceEmbarque);
		//		System.out.println("Indice de desembarque " + indiceDesembarque);


		////		indiceEmbarque = (int)( (Math.random() * (rota2.size()/2)));
		//		rota2.add(indiceEmbarque, elementoDesembarque );
		////		indiceDesembarque= (int)((rota2.size()/2)+ (Math.random() * (rota2.size())));
		//		rota2.add(indiceDesembarque, elementoDesembarque );
		//		System.out.println("Rota 1 : "+ rota1.toString());
		//		System.out.println("Rota 2 : "+ rota2.toString());
		//
		//		//		LinkedList<Integer> rota1, rota2 ;
		//		int elementoRandomica = (int) ( (Math.random() * rota1.size()));
		//		int elementoEntra = rota1.get(elementoRandomica);
		//		int elementoSai = rota1.get(2*elementoRandomica);
		//		rota1.remove(elementoEntra);
		//		rota1.remove(elementoSai);

		rota2.add(indiceEmbarque,elementoEmbarque);
		rota2.add(indiceDesembarque, elementoDesembarque);
		//		System.out.println("Rota 1 : "+ rota1.toString()+" removidos, >>tamanho "+ rota1.size());
		//		System.out.println("Rota 2 : "+ rota2.toString()+" removidos >>tamanho "+ rota2.size());




		so.get(nRota2Randomica).adicionaA(indiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaB(indiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaD(indiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaR(indiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaW(indiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaQ(indiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaT(indiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaF(indiceEmbarque, 0);
		//	System.out.println("Tamanho das variaveis "+so.get(nRota1Randomica).getA().size());		


		so.get(nRota2Randomica).adicionaA(indiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaB(indiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaD(indiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaR(indiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaW(indiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaQ(indiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaT(indiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaF(indiceDesembarque, 0);
		//		System.out.println("Tamanho das variaveis "+so.get(nRota2Randomica).getA().size());

		so.get(nRota1Randomica).setRota(rota1);
		so.get(nRota2Randomica).setRota(rota2);
		System.out.println(" ======================== Fim do Realoca Rota ========================");
		return so;
	}

	/**
	 * 
	 * @param so
	 * @return
	 */
	public ArrayList<Rota> trocaPontos(ArrayList<Rota> so){//rota1,LinkedList<Integer> rota2 ){
		System.out.println(" ======================== Inicio Troca Pontos ========================");

		int nRota1Randomica = (int) ((Math.random() * so.size())), 
		nRota2Randomica;
		do {
			nRota2Randomica = (int) ((Math.random() * so.size()));

		} while (nRota1Randomica == nRota2Randomica );//Seleciona outra rota aleatoria

		LinkedList<Integer> rota1 = so.get(nRota1Randomica).getRota();//Seleciona uma rota aleatoria
		LinkedList<Integer> rota2 = so.get(nRota2Randomica).getRota();

		if((rota1.size() == 2)||(rota2.size() == 2)){
			System.out.println("Acabou");
			System.out.println(" ======================== Fim do Troca Pontos ========================");
			return so;	
		}

		int indiceRandomico = (int)(1+ (Math.random() * (rota1.size()-2)));//Somente os embarques e desembarques//rota1.size()/2));

		int //indiceElemEmbarque = rota1.get(indiceRandomico), 
		indiceDesembarque = 0;

		//int indiceElemDesembarque = rota1.get(elementoRandomica);
		//int elementoEntra = rota1.get(elementoRandomica);
		//		System.out.println("Limites dos Embarques" + limiteDosEmbarques);
		//		System.out.println("A  Tamanho: "+so.get(nRota1Randomica).getA().size()+">>" +so.get(nRota1Randomica).getA().toString());
		//		System.out.println("B Tamanho: "+so.get(nRota1Randomica).getB().size()+">>" +so.get(nRota1Randomica).getB().toString());
		//		System.out.println("D Tamanho: "+so.get(nRota1Randomica).getD().size()+">>" +so.get(nRota1Randomica).getD().toString());
		//		System.out.println("R Tamanho: "+so.get(nRota1Randomica).getR().size()+">>" +so.get(nRota1Randomica).getR().toString());
		//		System.out.println("w Tamanho: "+so.get(nRota1Randomica).getW().size()+">>" +so.get(nRota1Randomica).getW().toString());
		//		System.out.println("T Tamanho: "+so.get(nRota1Randomica).getT().size()+">>" +so.get(nRota1Randomica).getT().toString());
		//		System.out.println("Q Tamanho: "+so.get(nRota1Randomica).getQ().size()+">>" +so.get(nRota1Randomica).getQ().toString());
		//		System.out.println("F Tamanho: "+so.get(nRota1Randomica).getF().size()+">>" +so.get(nRota1Randomica).getF().toString());
		//
		//		System.out.println("================================");
		//		System.out.println("Rota 1"+"Tamanho"+rota1.size() +rota1.toString());
		//		System.out.println("Rota 2"+"Tamanho"+rota2.size() +rota2.toString());


		Integer elementoEmbarque = 0,elementoDesembarque;

		do{
			indiceRandomico = (int)(1+ (Math.random() * (rota1.size()-2)));
			//			System.out.println("Indice Randomico " + indiceRandomico);
			elementoEmbarque = rota1.get(indiceRandomico);//Retorna o id
			//			System.out.println("592 Elemento de Embarque  "+ elementoEmbarque );

		}while(elementoEmbarque > limiteDosEmbarques);


		elementoDesembarque = elementoEmbarque + limiteDosEmbarques;
		indiceDesembarque = rota1.indexOf(elementoDesembarque);//Retorna o id do desembarque

		//		elementoDesembarque = rota1.get(indiceDesembarque);//
		//		System.out.println("592 Elemento de Desembarque  "+ (elementoEmbarque + limiteDosEmbarques));
		//int indiceSai = rota1.indexOf(elementoRandomica);

		rota1.remove(elementoEmbarque);//remove(elementoEntra);
		rota1.remove(elementoDesembarque);
		//Selecionando as variaveis de cada elemento da rota modificado

		//		System.out.println("A  Tamanho: "+so.get(nRota1Randomica).getA().size()+">>" +so.get(nRota1Randomica).getA().toString());
		//		System.out.println("B Tamanho: "+so.get(nRota1Randomica).getB().size()+">>" +so.get(nRota1Randomica).getB().toString());
		//		System.out.println("D Tamanho: "+so.get(nRota1Randomica).getD().size()+">>" +so.get(nRota1Randomica).getD().toString());
		//		System.out.println("R Tamanho: "+so.get(nRota1Randomica).getR().size()+">>" +so.get(nRota1Randomica).getR().toString());
		//		System.out.println("w Tamanho: "+so.get(nRota1Randomica).getW().size()+">>" +so.get(nRota1Randomica).getW().toString());
		//		System.out.println("T Tamanho: "+so.get(nRota1Randomica).getT().size()+">>" +so.get(nRota1Randomica).getT().toString());
		//		System.out.println("Q Tamanho: "+so.get(nRota1Randomica).getQ().size()+">>" +so.get(nRota1Randomica).getQ().toString());
		//		System.out.println("F Tamanho: "+so.get(nRota1Randomica).getF().size()+">>" +so.get(nRota1Randomica).getF().toString());

		so.get(nRota1Randomica).removetA(indiceRandomico);
		so.get(nRota1Randomica).removetB(indiceRandomico);
		so.get(nRota1Randomica).removetD(indiceRandomico);
		so.get(nRota1Randomica).removetR(indiceRandomico);
		so.get(nRota1Randomica).removetW(indiceRandomico);
		so.get(nRota1Randomica).removetQ(indiceRandomico);
		so.get(nRota1Randomica).removetT(indiceRandomico);
		so.get(nRota1Randomica).removetF(indiceRandomico);

		//Removendo "e, l , s ,acao" do desembarque
		so.get(nRota1Randomica).removetA(indiceDesembarque);
		so.get(nRota1Randomica).removetB(indiceDesembarque);
		so.get(nRota1Randomica).removetD(indiceDesembarque);
		so.get(nRota1Randomica).removetR(indiceDesembarque);
		so.get(nRota1Randomica).removetW(indiceDesembarque);
		so.get(nRota1Randomica).removetQ(indiceDesembarque);
		so.get(nRota1Randomica).removetT(indiceDesembarque);
		so.get(nRota1Randomica).removetF(indiceDesembarque);
		//rota1.remove(elementoDesembarque);
		int elementoIndiceDesembarque, elementoIndiceEmbarque;// = (int)(1+ (Math.random() * (rota1.size()-2)));

		do{
			elementoIndiceEmbarque = (int)(1+ (Math.random() * (rota2.size()-2)));
			elementoIndiceDesembarque = (int)(1+ (Math.random() * (rota2.size()-2)));
		}while(elementoIndiceEmbarque > elementoIndiceDesembarque || elementoEmbarque == elementoDesembarque );

		//Adicona na rota2 os valores das variaveis de embarque
		rota2.add(elementoIndiceEmbarque, elementoEmbarque);		

		so.get(nRota2Randomica).adicionaA(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaB(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaD(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaR(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaW(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaQ(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaT(elementoIndiceEmbarque, 0);
		so.get(nRota2Randomica).adicionaF(elementoIndiceEmbarque, 0);
		//Adicona na rota2 os valores das variaveis de desembarque		
		rota2.add(elementoIndiceDesembarque, elementoDesembarque);

		so.get(nRota2Randomica).adicionaA(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaB(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaD(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaR(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaW(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaQ(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaT(elementoIndiceDesembarque, 0);
		so.get(nRota2Randomica).adicionaF(elementoIndiceDesembarque, 0);

		so.get(nRota1Randomica).setRota(rota1);
		so.get(nRota2Randomica).setRota(rota2);
		System.out.println(" ======================== Fim do Troca Pontos ========================");
		return so;

	}

	public ArrayList<Rota> realocaBlocosEmbarque(ArrayList<Rota> so){
		System.out.println(" ======================== Inicio do Realoca Blocos ========================");

		int nRota1Randomica = (int) ((Math.random() * so.size())), 
		count = 1; 
		LinkedList<Integer> rota = so.get(nRota1Randomica).getRota();//Seleciona uma rota aleatoria
		LinkedList<Integer> aInverter = new LinkedList<Integer>();
		Integer elemento = 0;
		//		System.out.println("Rota para Realocar Bloco "+ rota.toString());
		for (int i = 1; i < rota.size(); i++) {
			elemento = (Integer) rota.get(i);
			//			System.out.println("Elemento "+ elemento);

			if(elemento < limiteDosEmbarques){
				aInverter.add(i-1, elemento);
				//				System.out.println("Elemento a ser invertido");

			}else 
				break;
		}

		//		System.out.println("Rota invertida "+ aInverter.toString());
		//		System.out.println("Entrou no laco");
		for (int i = 0; i < aInverter.size(); i++) {
			//			System.out.println("Iteracao "+i+ " valor "+(aInverter.size() - i));
			//			System.out.println(aInverter.get((aInverter.size() - (i+1))));
			rota.remove(i+1);
			rota.add(i+1,aInverter.get((aInverter.size() - (i+1))));
		}
		//		System.out.println("Saiu no laco");
		//		System.out.println(rota.toString());
		so.get(nRota1Randomica).setRota(rota);



		//		do{
		//			elemento = (Integer) rota.get(count);
		//			aInverter.add(count, elemento);
		//
		//			System.out.println("Elemento a ser invertido");
		//			count++;
		//		}while(elemento > limiteDosEmbarques);
		//
		//		for (int i = aInverter.size(); i> 0; i--) {
		//			rota.set(i, aInverter.get(i));
		//		}


		System.out.println(" ======================== Fim do Realoca Blocos ========================");
		return so;

	}

}








